/* Sliding Rooks solution with animation
 * $ cc -Ofast -o rooks rooks.c
 * $ ./rooks | mpv --no-correct-pts --fps=60 -
 * $ ./rooks | x264 --fps=60 -o rooks.mp4 /dev/stdin
 * Ref: https://possiblywrong.wordpress.com/2020/05/20/sliding-rooks-and-queens/
 * Ref: https://nullprogram.com/video/?v=rooks
 */
#include <stdio.h>

static const unsigned char value_pal[] = {0x00, 0x67, 0x94, 0xff};
static const unsigned char value_rle[] = {
    0xff, 0xff, 0xff, 0x31, 0xf8, 0x01, 0x00, 0x01, 0x01, 0x01, 0xff,
    0x01, 0xf8, 0x01, 0x00, 0x02, 0x2f, 0x01, 0xff, 0x01, 0x40, 0x01,
    0x00, 0x01, 0x2f, 0x01, 0xff, 0x08, 0xf8, 0x01, 0x00, 0x02, 0xff,
    0x01, 0xf8, 0x01, 0x00, 0x02, 0x2f, 0x01, 0xff, 0x01, 0x00, 0x02,
    0x2f, 0x01, 0xff, 0x08, 0xf8, 0x01, 0x00, 0x02, 0xff, 0x01, 0xf8,
    0x01, 0x00, 0x02, 0x2f, 0x01, 0xff, 0x01, 0x00, 0x02, 0x2f, 0x01,
    0xff, 0x08, 0xf8, 0x01, 0x00, 0x02, 0x55, 0x01, 0x50, 0x01, 0x00,
    0x02, 0x05, 0x01, 0x55, 0x01, 0x00, 0x02, 0x2f, 0x01, 0xff, 0x08,
    0xf8, 0x01, 0x00, 0x0a, 0x2f, 0x01, 0xff, 0x08, 0xf8, 0x01, 0x00,
    0x0a, 0x2f, 0x01, 0xff, 0x08, 0xf8, 0x01, 0x00, 0x0a, 0x2f, 0x01,
    0xff, 0x08, 0xf8, 0x01, 0x00, 0x0a, 0x2f, 0x01, 0xff, 0x08, 0xf4,
    0x01, 0x00, 0x0a, 0x1f, 0x01, 0xff, 0x08, 0xf7, 0x01, 0xff, 0x0a,
    0xdf, 0x01, 0xff, 0x08, 0xf6, 0x01, 0xff, 0x0a, 0x9f, 0x01, 0xff,
    0x08, 0xfe, 0x01, 0x00, 0x0a, 0xbf, 0x01, 0xff, 0x09, 0xc0, 0x01,
    0x00, 0x08, 0x03, 0x01, 0xff, 0x0a, 0xf4, 0x01, 0x6a, 0x01, 0xaa,
    0x06, 0xa9, 0x01, 0x1f, 0x01, 0xff, 0x0a, 0xfd, 0x01, 0xff, 0x08,
    0x7f, 0x01, 0xff, 0x0a, 0xfe, 0x01, 0x00, 0x08, 0xbf, 0x01, 0xff,
    0x0b, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08,
    0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00,
    0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c,
    0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff,
    0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08,
    0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00,
    0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c,
    0x00, 0x08, 0xff, 0x0b, 0xfe, 0x01, 0x55, 0x08, 0xbf, 0x01, 0xff,
    0x0a, 0xfd, 0x01, 0xff, 0x08, 0x7f, 0x01, 0xff, 0x0a, 0xfc, 0x01,
    0x15, 0x01, 0x55, 0x06, 0x54, 0x01, 0x3f, 0x01, 0xff, 0x0a, 0xf4,
    0x01, 0x00, 0x08, 0x1f, 0x01, 0xff, 0x0a, 0xeb, 0x01, 0xff, 0x08,
    0xeb, 0x01, 0xff, 0x0a, 0x4b, 0x01, 0xff, 0x08, 0xe1, 0x01, 0xff,
    0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x00, 0x0a,
    0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x7f,
    0x01, 0xff, 0x08, 0xfd, 0x01, 0xff, 0x08, 0xfc, 0x01, 0x00, 0x01,
    0x7f, 0x01, 0xff, 0x08, 0xfd, 0x01, 0x00, 0x01, 0x3f, 0x01, 0xff,
    0x06, 0xfc, 0x01, 0x00, 0x0c, 0x3f, 0x01, 0xff, 0x06, 0xfc, 0x01,
    0x00, 0x0c, 0x3f, 0x01, 0xff, 0x06, 0xfc, 0x01, 0x00, 0x0c, 0x3f,
    0x01, 0xff, 0x06, 0xfc, 0x01, 0x00, 0x0c, 0x3f, 0x01, 0xff, 0x06,
    0xfc, 0x01, 0x00, 0x0c, 0x3f, 0x01, 0xff, 0x06, 0xfc, 0x01, 0x00,
    0x0c, 0x3f, 0x01, 0xff, 0x06, 0xfe, 0x01, 0xaa, 0x0c, 0xbf, 0x01,
    0xff, 0xb7
};
static const unsigned char alpha_pal[] = {0x00, 0x6b, 0xa1, 0xff};
static const unsigned char alpha_rle[] = {
    0x00, 0xff, 0x00, 0x31, 0x07, 0x01, 0xff, 0x01, 0xfe, 0x01, 0x00,
    0x01, 0x07, 0x01, 0xff, 0x02, 0xd0, 0x01, 0x00, 0x01, 0xbf, 0x01,
    0xff, 0x01, 0xd0, 0x01, 0x00, 0x08, 0x0b, 0x01, 0xff, 0x02, 0x00,
    0x01, 0x0b, 0x01, 0xff, 0x02, 0xe0, 0x01, 0x00, 0x01, 0xff, 0x02,
    0xe0, 0x01, 0x00, 0x08, 0x0b, 0x01, 0xff, 0x02, 0x00, 0x01, 0x0b,
    0x01, 0xff, 0x02, 0xe0, 0x01, 0x00, 0x01, 0xff, 0x02, 0xe0, 0x01,
    0x00, 0x08, 0x0b, 0x01, 0xff, 0x02, 0xaa, 0x01, 0xaf, 0x01, 0xff,
    0x02, 0xfa, 0x01, 0xaa, 0x01, 0xff, 0x02, 0xe0, 0x01, 0x00, 0x08,
    0x0b, 0x01, 0xff, 0x0a, 0xe0, 0x01, 0x00, 0x08, 0x0b, 0x01, 0xff,
    0x0a, 0xe0, 0x01, 0x00, 0x08, 0x0b, 0x01, 0xff, 0x0a, 0xe0, 0x01,
    0x00, 0x08, 0x0b, 0x01, 0xff, 0x0a, 0xe0, 0x01, 0x00, 0x08, 0x0b,
    0x01, 0xff, 0x0a, 0xe0, 0x01, 0x00, 0x08, 0x0f, 0x01, 0xff, 0x0a,
    0xf0, 0x01, 0x00, 0x08, 0x0b, 0x01, 0xff, 0x0a, 0xe0, 0x01, 0x00,
    0x08, 0x01, 0x01, 0xff, 0x0a, 0x40, 0x01, 0x00, 0x09, 0x3f, 0x01,
    0xff, 0x08, 0xfc, 0x01, 0x00, 0x0a, 0x0f, 0x01, 0xff, 0x08, 0xf0,
    0x01, 0x00, 0x0a, 0x03, 0x01, 0xff, 0x08, 0xc0, 0x01, 0x00, 0x0a,
    0x01, 0x01, 0xff, 0x08, 0x40, 0x01, 0x00, 0x0b, 0xff, 0x08, 0x00,
    0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08,
    0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff,
    0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c,
    0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00,
    0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08,
    0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff,
    0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0b,
    0x01, 0x01, 0xff, 0x08, 0x40, 0x01, 0x00, 0x0a, 0x02, 0x01, 0xff,
    0x08, 0x80, 0x01, 0x00, 0x0a, 0x03, 0x01, 0xff, 0x08, 0xc0, 0x01,
    0x00, 0x0a, 0x0b, 0x01, 0xff, 0x08, 0xe0, 0x01, 0x00, 0x0a, 0x1f,
    0x01, 0xff, 0x08, 0xf4, 0x01, 0x00, 0x0a, 0xbf, 0x01, 0xff, 0x08,
    0xfe, 0x01, 0x00, 0x0a, 0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x00,
    0x0a, 0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a,
    0x00, 0x0a, 0xff, 0x0a, 0x00, 0x08, 0x03, 0x01, 0xff, 0x0c, 0xc0,
    0x01, 0x00, 0x06, 0x03, 0x01, 0xff, 0x0c, 0xc0, 0x01, 0x00, 0x06,
    0x03, 0x01, 0xff, 0x0c, 0xc0, 0x01, 0x00, 0x06, 0x03, 0x01, 0xff,
    0x0c, 0xc0, 0x01, 0x00, 0x06, 0x03, 0x01, 0xff, 0x0c, 0xc0, 0x01,
    0x00, 0x06, 0x03, 0x01, 0xff, 0x0c, 0xc0, 0x01, 0x00, 0x06, 0x03,
    0x01, 0xff, 0x0c, 0xc0, 0x01, 0x00, 0x06, 0x01, 0x01, 0x55, 0x0c,
    0x40, 0x01, 0x00, 0xb7
};

// Unpack 24-bit (4 6-bit elements) representation into a bitboard.
static unsigned long long
unpack(long state)
{
    return 1ULL << (state       & 0x3f) |
           1ULL << (state >>  6 & 0x3f) |
           1ULL << (state >> 12 & 0x3f) |
           1ULL << (state >> 18       );
}

// Pack bitboard into 24-bit (4 6-bit elements) representation.
static long
pack(unsigned long long board)
{
    long a = __builtin_ctzll(board); board &= ~(1ULL << a);
    long b = __builtin_ctzll(board); board &= ~(1ULL << b);
    long c = __builtin_ctzll(board); board &= ~(1ULL << c);
    long d = __builtin_ctzll(board);
    return a<<18 | b<<12 | c<<6 | d;
}

// Populate r with neighboring states.
static int
neighbors(long state, long *r)
{
    unsigned long long board = unpack(state);
    int c = 0;
    for (int i = 0; i < 4; i++) {
        int found;
        int v = state>>(6*i) & 0x3f;

        found = 0;
        for (int d = 8; d < 64; d += 8) {
            if (v - d >= 0 && !((1ULL<<(v - d)) & board)) {
                unsigned long long n = board;
                n |= 1ULL << (v - d);
                n &= ~(1ULL << v);
                r[c] = pack(n);
                found = 1;
            } else {
                break;
            }
        }
        c += found;

        found = 0;
        for (int d = 8; d < 64; d += 8) {
            if (v + d < 64 && !((1ULL<<(v + d)) & board)) {
                unsigned long long n = board;
                n |= 1ULL << (v + d);
                n &= ~(1ULL << v);
                r[c] = pack(n);
                found = 1;
            } else {
                break;
            }
        }
        c += found;

        found = 0;
        for (unsigned d = 1; d < 8; d++) {
            if ((v - d)>>3 == (unsigned)v>>3 && !((1ULL<<(v - d)) & board)) {
                unsigned long long n = board;
                n |= 1ULL << (v - d);
                n &= ~(1ULL << v);
                r[c] = pack(n);
                found = 1;
            } else {
                break;
            }
        }
        c += found;

        found = 0;
        for (unsigned d = 1; d < 8; d++) {
            if ((v + d)>>3 == (unsigned)v>>3 && !((1ULL<<(v + d)) & board)) {
                unsigned long long n = board;
                n |= 1ULL << (v + d);
                n &= ~(1ULL << v);
                r[c] = pack(n);
                found = 1;
            } else {
                break;
            }
        }
        c += found;
    }
    return c;
}

// Raw image data
static unsigned char buf[640][640][3];
static unsigned char alpha[80][20];
static unsigned char value[80][20];

static void
uncompress(unsigned char dst[80][20], const unsigned char *rle)
{
    unsigned char *p = (void *)dst;
    for (int i = 0; i < 80*20;) {
        int v = *rle++;
        int r = *rle++;
        for (int j = 0; j < r; j++, i++) {
            p[i] = v;
        }
    }
}

static int
frame(void)
{
    puts("P6\n640 640\n255");
    return !fwrite(buf, sizeof(buf), 1, stdout);
}

static void
put(int x, int y, long c)
{
    buf[y][x][0] = c >> 16;
    buf[y][x][1] = c >>  8;
    buf[y][x][2] = c >>  0;
}

static long
get(int x, int y)
{
    return (long)buf[y][x][0] << 16 |
           (long)buf[y][x][1] <<  8 |
           (long)buf[y][x][2] <<  0;
}

static void
clear(void)
{
    static const long colors[] = {0xffce9eL, 0xd18b47L};
    for (int y = 0; y < 640; y++) {
        for (int x = 0; x < 640; x++) {
            put(x, y, colors[(x/80+y/80)%2]);
        }
    }
}

static long
blend(long c0, long c1, float a)
{
    float r0 = ((c0 >> 16)       )/255.0f;
    float g0 = ((c0 >>  8) & 0xff)/255.0f;
    float b0 = ( c0        & 0xff)/255.0f;
    float r1 = ((c1 >> 16)       )/255.0f;
    float g1 = ((c1 >>  8) & 0xff)/255.0f;
    float b1 = ( c1        & 0xff)/255.0f;
    float r = r0*a + r1*(1-a);
    float g = g0*a + g1*(1-a);
    float b = b0*a + b1*(1-a);
    return (long)(r*255) << 16 |
           (long)(g*255) <<  8 |
           (long)(b*255) <<  0;
}

static void
rook(int x, int y)
{
    for (int py = 0; py < 80; py++) {
        for (int px = 0; px < 80; px++) {
            int dx = x + px;
            int dy = y + py;
            if (dx >= 0 && dx < 640 && dy >= 0 && dy < 640) {
                long v  = value_pal[value[py][px/4] >> (2*(3-px%4)) & 3];
                float a = alpha_pal[alpha[py][px/4] >> (2*(3-px%4)) & 3]/255.0f;
                long f = v<<16|v<<8|v;
                long b = get(dx, dy);
                put(dx, dy, blend(f, b, a));
            }
        }
    }
}

static void
draw(long state)
{
    unsigned long long board = unpack(state);
    clear();
    for (int y = 0; y < 8; y++) {
        for (int x = 0; x < 8; x++) {
            if (board >> (y*8 + x) & 1) {
                rook(x*80, y*80);
            }
        }
    }
}

static int
slide(long s0, long s1)
{
    unsigned long long b0 = unpack(s0);
    unsigned long long b1 = unpack(s1);
    int src = __builtin_ctzll(b0 & (b0 ^ b1));
    int dst = __builtin_ctzll(b1 & (b0 ^ b1));
    int srcx = src%8*80;
    int srcy = src/8*80;
    int dstx = dst%8*80;
    int dsty = dst/8*80;
    int dx = dstx - srcx;
    int speed = 8; // must evenly divide 80
    if (dx < 0) dx = -speed;
    if (dx > 0) dx = +speed;
    int dy = dsty - srcy;
    if (dy < 0) dy = -speed;
    if (dy > 0) dy = +speed;
    for (; srcx != dstx || srcy != dsty; srcx += dx, srcy += dy) {
        clear();
        unsigned long long fixed = b0 & b1;
        for (int i = 0; i < 3; i++) {
            int p = __builtin_ctzll(fixed);
            fixed &= ~(1ULL << p);
            int x = p%8*80;
            int y = p/8*80;
            rook(x, y);
        }
        rook(srcx, srcy);
        if (frame()) return 1;
    }
    rook(dstx, dsty);
    return frame();
}

int
main(void)
{
    long init = 7L<<12 | 56L<<6 | 63L;
    long goal = 27L<<18 | 28L<<12 | 35L<<6 | 36L;

    #ifdef _WIN32
    /* Set stdout to binary mode. */
    int _setmode(int, int);
    _setmode(1, 0x8000);
    #endif

    #define N (sizeof(long)*8)
    #define GET(v) (seen[v/N] &  1UL<<(v%N))
    #define SET(v) (seen[v/N] |= 1UL<<(v%N))
    static unsigned long seen[(1L<<24)/N];

    static struct {
        long state;
        long parent;
    } queue[1L<<20];
    long tail = 0;
    long head = 0;

    SET(init);
    queue[head].state = init;
    queue[head++].parent = -1;

    uncompress(value, value_rle);
    uncompress(alpha, alpha_rle);

    clear();
    draw(init);
    for (int i = 0; i < 60*1; i++) {
        if (frame()) return 1;
    }

    while (head != tail) {
        long state = queue[tail].state;
        if (state == goal) {
            /* Render the solution */
            int n = 0;
            long i = tail;
            long chain[64];
            do {
                chain[n++] = i;
                i = queue[i].parent;
            } while (i >= 0);
            for (n -= 2; n >= 0; n--) {
                slide(queue[chain[n+1]].state, queue[chain[n]].state);
            }
            clear();
            draw(state);
            for (int i = 0; i < 60*2; i++) {
                if (frame()) return 1;
            }
            break;
        }
        long parent = tail++;

        long ns[16];
        int c = neighbors(state, ns);
        for (int i = 0; i < c; i++) {
            long n = ns[i];
            if (!GET(n)) {
                SET(n);
                queue[head].state = n;
                queue[head++].parent = parent;
            }
        }
    }
}
